1. Field of the Invention
The present invention generally relates to electronic circuits and, more specifically, to circuits generating prime numbers. The present invention more specifically relates to the protection of the generation of prime numbers in an electronic circuit against side channel attacks, for example, by statistical analysis of the power consumption of the circuit (SPA—simple power analysis) or of its electromagnetic signature.
The present invention more specifically applies to circuits executing RSA-type asymmetrical encryption algorithms and more generally algorithms exploiting a prime number factorization.
2. Discussion of the Related Art
The RSA algorithm is one of the most commonly used asymmetrical encryption algorithms (with a public key). This algorithm is used to encrypt/decrypt data or to sign data and enable them to be authenticated. It is based on the use of a pair of keys comprising a public key and a private key. In encryption/decryption mode, the public key is used by a transmitter to encrypt data to be confidentially communicated to a receiver, the latter using its private (or secret) key to decrypt the data. For an authentication, the private key is used by the transmitter to sign the data while the public key is used by the receiver to authenticate the signature.
The public key is relatively widely accessible, to enable the transmitter of the encrypted data or the receiver of the signed data to exploit these data. However, the private key is reserved to the circuit having created the pair of keys. The holder of the pair of keys may directly communicate the public key to the other party to enable it to process the data.
The generation of the pair of public and private keys requires the use of two different prime numbers “p” and “q”, of relatively large size (typically, 1,024 or 2,048 bits). The product of these prime numbers provides encryption modulus “n”. Numbers p and q are selected so that numbers p−1 and q−1 are prime with a quantity “e”, called public exponent, which is then prime with the Euler indicator “φ(n)” of product n (φ(n)=(p−1)(q−1)). As a result, there exists an integer “d” such that product e*d is congruent to 1 modulo φ(n). Pair n and e forms the public key while pair n and d forms the private key. Private exponent d is the inverse of exponent e, modulo (p−1)(q−1). Prime numbers p and q are only present in the circuit containing the private key.
The robustness of the RSA algorithm depends on prime numbers p and q. To “break” the RSA algorithms based on the public key, one needs to be able to factorize number n, and thus to obtain prime numbers p and q. Once this factorization is known, private exponent d can be calculated from public exponent e (d is obtained by calculating the inverse of e modulo (p−1)(q−1)). It is currently considered that by using modules n of a sufficient size (typically on the order of 1,500 bits), current algorithms do not enable, within a reasonable time, to factorize number n.
However, the introduction of numbers p and q into the electronic circuit or their generation by this circuit is particularly critical in terms of security, since their discovery by a hacker at this time of the circuit life provides him with the factorization of number n.
A first technique for generating RSA keys comprises generating these keys outside of the electronic circuit. Quantities p and q are introduced into the electronic circuit in a customization phase. This technique is not responsive to side channel attacks since the keys are not generated by the actual electronic circuit.
A second known technique comprises having the actual electronic circuit generate the prime numbers in a secure environment (in practice in a protected installation, with a reserved access). With this technique, attacks are not a problem either during the prime number generation.
However, more and more often, electronic circuits need to be able to generate their RSA keys outside of such secure environments. This, for example, enables to regenerate new keys in the case where a previous key has been repudiated (key assumed to have been hacked). Such a generation is for example performed during a customization of the electronic circuit in a non-secure environment or during a first use. According to an example of application to electronic passports, the key is desired to be generated by the electronic chip contained in the passport once it is in its holder's hands. Thus, this key cannot have been previously used in a passport authentication procedure.
Public exponent e may be a parameter of the public key infrastructure (PKI) and is the same for all keys. It is for example introduced into the electronic circuit during the manufacturing thereof (in a ROM) or during a customization phase (in an EEPROM).
Public exponent e may also be generated by the electronic circuit, for example, by selection of a random number, and may then be communicated to the elements with which the circuit must communicate.
The public key (public exponent and encryption modulus) is thus either known by the receiver (signature) or by the transmitter (encryption), or communicated thereto (for each transaction or once and for all) by the electronic circuit holding the private key. The public key further needs generally be certified.
The generation of large prime numbers is expensive in terms of time and calculation. In particular, so-called primality tests, which enable to validate or not the primality of a number, generally implement modular exponentiations requiring a significant amount of calculations (for example, the so-called Miller-Rabin primality test). This is why it is desired to only perform such tests for candidate numbers already having successfully passed tests with respect to relatively small prime numbers. Such tests correspond to divisions by relatively small prime numbers or to comparisons with respect to prime number tables. For example, a Miller-Rabin test can be performed with a small base (two, for example) or a largest common divider calculation may be performed (for example, adding bytes modulo 255 to obtain a result smaller than 255 and then calculate the largest common divider of this result with 255. If it is different from 1, a single test can tell that the number is not divisible by the three factors of 255, that is, 3, 5, and 17).
When the prime numbers are generated by the electronic circuit in a non-secure environment, the circuit is likely to undergo side-channel attacks (SPA or electromagnetic analysis). In particular, such attacks may occur in primality tests executing divisions or comparisons with prime number tables.